//找到字符串中所有字母异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int>res;
        int hash1[26]={0};
        int hash2[26]={0};
        int count=0;//count标记的是有效字母的个数
        //有效指的是s中当前字符是p需要的 且次数不超过p总共需要的次数
        //当s和p的“有效字母个数”相同 就证明了构成了异位词
        for(auto ch:p) hash1[ch-'a']++;
        for(int l=0,r=0;r<s.size();r++)
        {
            //进窗口
            char ch=s[r];
            hash2[ch-'a']++;
            //使用count来记录有效的字母个数
            if(hash2[ch-'a']<= hash1[ch-'a'])
            {
                //s中该位置的字母出现次数 小于 p中该字母的出现次数
                //说明这个字母被需要
                count++;
            }

            //出窗口
            if(r-l+1 > p.size()) 
            {
                char out=s[l];
                l++;
                if(hash2[out-'a'] <= hash1[out-'a']) 
                {
                    count--;
                }
                hash2[out-'a']--;
            }
            if(count==p.size()) res.push_back(l);
        }
        return res;
    }
};
//串联所有单词的子串
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        //将words中每个string 看成一个整体 那s自然也就成了一个整体的集合
        //问题就转变成了在s中寻找字母异位词
        vector<int>res;
        unordered_map<string,int> hash1;
        for(auto e:words) hash1[e]++;
        int len=words[0].size();
        int m=words.size();//words中整体的个数
        //由于从哪个位置将s进行拆分成len长度的整体有多种情况
        //所以需要每种情况都考虑到
        for(int i=0;i<len;i++)
        {
            unordered_map<string,int>hash2;
            // abcde  m=3
            //   r  
            for(int l=i,r=i,count=0;r+len <=s.size();r+=len)
            {
                string in=s.substr(r,len);
                hash2[in]++;
                if(hash2[in] <= hash1[in]) count++;
                if(r-l+1 >len*m )
                {
                    string out=s.substr(l,len);
                    if(hash2[out]<= hash1[out]) count--;
                    hash2[out]--;
                    l+=len;
                }
                if(count==m) res.push_back(l);
            }
        }
        return res;
    }
};

//最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        int hash1[128]={0};
        int kind=0;//统计有效字符的种类
        for(auto ch:t) 
        {
            if(hash1[ch]==0)
            {
                kind++;
            }
            hash1[ch]++;
        }
        int hash2[128]={0};
        int minlen=INT_MAX,begin=-1;
        for(int l=0,r=0,count=0;r<s.size();r++)
        {
            char in=s[r];
            hash2[in]++;//入窗口
            if(hash2[in]==hash1[in]) count++; 
            //只有在刚好相等的情况下改变count 表示有一种字符准备就绪了
            while(count==kind)
            {
                //此时窗口内 满足了所有的字符 先更新结果 然后开始缩小区间
                if(r-l+1<minlen)
                {
                    minlen=r-l+1;
                    begin=l;
                }
                char out=s[l];
                if(hash2[out]==hash1[out]) count--;
                hash2[out]--;
                l++;
            }
        }
        if(begin==-1) return "";
        else return s.substr(begin,minlen);

    }
};
